/**
 * FileName:Exercise1404.c
 * ------------------------------------------------------------------------------------------------------------
 * 14.4 Write a program to find values of `a` and `M`, with `M` as small as possible, such that
 * the hash function `a*x % M` produces distinct values (no collisions) for the keys in Figure 14.2.
 * The result is an example of a perfect hash function.
 * ------------------------------------------------------------------------------------------------------------
 */

#include <stdio.h>
#include <stdbool.h> // For bool type
#include <stdlib.h>

//函数声明
int calculate_hash(int, int, int);
// Function to calculate hash value h(x) = (a * x) % M
int calculate_hash(int x, int a, int M) {
    // Use long long for intermediate multiplication to prevent overflow
    // if a * x exceeds INT_MAX before modulo operation.
    return (int)(((long long)a * x) % M);
}

//测试函数声明
void test_hash();
int main(int argc, char *argv[]) {
    test_hash();
    return 0;
}

void test_hash() {
    // Keys from Figure 14.2
    int data[] = {16838, 5758, 10113, 17515, 31051, 5627, 23010, 7419,
                  16212, 4086, 2749, 12767, 9084, 12060, 32225, 17543,
                  25089, 21183, 25137, 25566, 26966, 4978, 20495, 10311, 11367};
    int num_keys = sizeof(data) / sizeof(data[0]); // Number of keys = 25

    printf("Finding a perfect hash function for Figure 14.2 keys...\n");

    // Start M from num_keys, as table size must be at least the number of keys
    for (int M = num_keys; ; M++) { // Loop M indefinitely until a solution is found
        // Iterate through possible 'a' values from 1 to M-1
        for (int a = 1; a < M; a++) {
            bool has_collision = false;
            bool *seen = (bool *)calloc(M, sizeof(bool)); // calloc initializes memory to zero (false)
            if (seen == NULL) {
                perror("Failed to allocate memory for 'seen' array");
                return ;
            }

            // Test all keys with current (a, M)
            for (int i = 0; i < num_keys; i++) {
                int key = data[i];
                int hash_val = calculate_hash(key, a, M);

                // Check if hash_val is within valid range [0, M-1]
                // This is guaranteed by % M operation if a*x is non-negative
                if (hash_val < 0 || hash_val >= M) {
                    // This should theoretically not happen with non-negative inputs and % M
                    // But as a safeguard:
                    has_collision = true; // Treat out-of-range as collision
                    break;
                }

                if (seen[hash_val]) { // Collision detected
                    has_collision = true;
                    break; // No need to test further keys for this (a, M) pair
                }
                seen[hash_val] = true; // Mark this slot as occupied
            }

            free(seen); // Free memory for 'seen' array

            if (!has_collision) {
                printf("Found perfect hash function:\n");
                printf("a = %d, M = %d\n", a, M);
                printf("Hash values for keys:\n");
                for (int i = 0; i < num_keys; i++) {
                    printf("Key: %d -> Hash: %d\n", data[i], calculate_hash(data[i], a, M));
                }
                return ; // Found the smallest M, exit program
            }
        }
    }
    return ; // Should not reach here if a solution exists
}
